﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace FindClosestPoints {
/// <summary>
/// MainWindow.xaml 的交互逻辑
/// </summary>
public partial class MainWindow : Window {
	public int GetRandomSeed ( ) {
		byte[] bytes = new byte[4];
		System.Security.Cryptography.RNGCryptoServiceProvider rng = new System.Security.Cryptography.RNGCryptoServiceProvider ( );
		rng.GetBytes ( bytes );
		return BitConverter.ToInt32 ( bytes, 0 );
	}
	private Line getDrawLine ( Point p1, Point p2 ) {

		Line l = new Line ( );

		l.Stroke = System.Windows.Media.Brushes.Blue;

		l.Y1 = RMartix[0, 0].ActualHeight / 2 + p1.X * RMartix[0, 0].ActualHeight;
		l.X1 = RMartix[0, 0].ActualWidth / 2 + p1.Y * RMartix[0, 0].ActualWidth;
		l.Y2 = RMartix[0, 0].ActualHeight / 2 + p2.X * RMartix[0, 0].ActualHeight;
		l.X2 = RMartix[0, 0].ActualWidth / 2 + p2.Y * RMartix[0, 0].ActualWidth;

		l.StrokeThickness = 3;
		l.HorizontalAlignment = HorizontalAlignment.Left;
		l.VerticalAlignment = VerticalAlignment.Center;

		return l;
	}
	private void rand_MouseWheel ( object sender, MouseWheelEventArgs e ) {
		if (e.Delta > 0)
			countSlider.Value++;
		else
			countSlider.Value--;
	}
	private void count_MouseWheel ( object sender, MouseWheelEventArgs e ) {
		if (e.Delta > 0)
			countSlider.Value++;
		else
			countSlider.Value--;
	}
	private void countSlider_MouseWheel ( object sender, MouseWheelEventArgs e ) {
		if (e.Delta > 0)
			countSlider.Value++;
		else
			countSlider.Value--;
	}
	int delay;
	private void speed_ValueChanged ( object sender, RoutedPropertyChangedEventArgs<double> e ) {
		delay = (int)speed.Value;
	}
	private double distance ( Point p1, Point p2 ) {
		return (p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y);
	}
	public MainWindow ( ) {
		InitializeComponent ( );
		this.Loaded += new RoutedEventHandler ( this.initCanvas );
	}
	Rectangle[,] RMartix;
	int[,] Martix;
	List<Point> Points;
	private void initCanvas ( object sender, RoutedEventArgs e ) {
		RMartix = new Rectangle[100, 100];
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				Rectangle r = new Rectangle ( );
				r.Width = canvas.ActualWidth / 100;
				r.Height = canvas.ActualHeight / 100;
				r.SetValue ( Canvas.TopProperty, i * r.Height );
				r.SetValue ( Canvas.LeftProperty, j * r.Width );
				canvas.Children.Add ( r );
				RMartix[i, j] = r;
				r.Fill = new SolidColorBrush ( Colors.White );
			}
		}
	}
	private void initData ( ) {
		if (lines != null) {
			foreach (Line l in lines) {
				Dispatcher.Invoke ( new Action ( ( ) => {
					canvas.Children.Remove ( l );
				} ) );
			}
			lines.Clear ( );
		}
		Points = new List<Point> ( );
		Martix = new int[100, 100];
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				if (Martix[i, j] != -1) {
					Martix[i, j] = -1;
					RMartix[i, j].Fill = new SolidColorBrush ( Colors.White );
				}
			}
		}
	}


	private void rand_Click ( object sender, RoutedEventArgs e ) {
		new Thread ( ( ) => {
			Dispatcher.Invoke ( new Action ( ( ) => {
				initData ( );
				int n = int.Parse ( count.Content.ToString ( ) );

				for (int i = 0; i < n; i++) {
					int x = new Random ( GetRandomSeed ( ) ).Next ( 0, 100 );
					int y = new Random ( GetRandomSeed ( ) ).Next ( 0, 100 );
					if (Martix[x, y] == -1) {
						Martix[x, y] = 1;
						Points.Add ( new Point ( x, y ) );
						RMartix[x, y].Fill = new SolidColorBrush ( Colors.Red );
					} else {
						i--;
					}
				}
			} ) );
		} ).Start ( );
	}
	Thread t;
	Line l,shortL,l2,l3,l4;
	List<Line> lines ;
	private void BFALG ( ) {
		t = new Thread ( ( ) => {
			if (lines != null) {
				foreach (Line l in lines) {
					Dispatcher.Invoke ( new Action ( ( ) => {
						canvas.Children.Remove ( l );
					} ) );
				}
				lines.Clear ( );
			}
			lines = new List<Line> ( );
			int shortest=-1;
			Dispatcher.Invoke ( new Action ( ( ) => {
				ProgressBar.Value = 0;
			} ) );
			for (int i = 0; i < Points.Count ( ); i++) {

				for (int j = i + 1; j < Points.Count ( ); j++) {

					Dispatcher.Invoke ( new Action ( ( ) => {
						l = getDrawLine ( Points.ElementAt ( i ), Points.ElementAt ( j ) );
						canvas.Children.Add ( l );
						lines.Add ( l );
					} ) );
					Thread.Sleep ( delay );
					int temp = (int)distance ( Points.ElementAt ( i ), Points.ElementAt ( j ) );
					if (shortest == -1 || temp < shortest) {
						shortest = temp;
						Dispatcher.Invoke ( new Action ( ( ) => {
							canvas.Children.Remove ( shortL );
							lines.Remove( shortL );
						} ) );
						shortL = l;
						Dispatcher.Invoke ( new Action ( ( ) => {
							shortL.Stroke = System.Windows.Media.Brushes.Green;
						} ) );
					}

					Dispatcher.Invoke ( new Action ( ( ) => {
						if (l != shortL) {
							canvas.Children.Remove ( l );
							lines.Remove ( l );
						}
					} ) );
				}
				Dispatcher.Invoke ( new Action ( ( ) => {
					ProgressBar.Value = (double)i  *100/ Points.Count ( );
				} ) );
			}
			Dispatcher.Invoke ( new Action ( ( ) => {
				ProgressBar.Value = 100;
				start.Content = "开始演示";
			} ) );
		} );


		t.SetApartmentState ( ApartmentState.STA );
		t.Start ( );

	}
	List<Line> tempLines = new List<Line> ( );
	private void DivideSolution ( ) {
		t = new Thread (()=> {
			//清理线段
			if (lines != null) {
				foreach (Line l in lines) {
					Dispatcher.Invoke ( new Action ( ( ) => {
						canvas.Children.Remove ( l );
					} ) );
				}
				lines.Clear ( );
			}
			lines = new List<Line> ( );


			LineWithPoints finalLWP = EffientClosestPair ( Points.OrderBy ( Point => Point.X ).ToList ( ), Points.OrderBy ( Point => Point.Y ).ToList ( ) );
			Console.WriteLine ( finalLWP.p1 + " : " + finalLWP.p2 );
			Dispatcher.Invoke ( new Action ( ( ) => {
				Line l = getDrawLine ( finalLWP.p1, finalLWP.p2 );
				canvas.Children.Add ( l );
				lines.Add ( l );
				Console.WriteLine ( "线" );
				start.Content = "开始演示";
			} ) );
		} );
		t.SetApartmentState ( ApartmentState.STA );
		t.Start ( );
	}

	private LineWithPoints EffientClosestPair (List<Point> PX, List<Point> PY) {
		LineWithPoints ret = new LineWithPoints ( );
		//if count<4 return
		if (PX.Count ( ) < 4) {
			double ans=-1;
			for (int i = 0; i < PX.Count ( ); i++) {
				for (int j = i + 1; j < PX.Count ( ); j++) {

					if (ans == -1 || distance ( PX.ElementAt ( i ), PX.ElementAt ( j ) ) < ans) {
						ret.p1 = PX.ElementAt ( i );
						ret.p2 = PX.ElementAt ( j );
						ans = distance ( PX.ElementAt ( i ), PX.ElementAt ( j ) );
					}
				}
			}

			return ret;
		}

		List<Point> XL = PX.Take ( PX.Count ( ) / 2 ).ToList ( ), XR = PX.Except(XL).ToList(),
		            YL=XL,YR=XR;
		YL=YL.OrderBy ( Point => Point.Y ).ToList();
		YR=YR.OrderBy ( Point => Point.Y ).ToList();
		Point p1 = new Point ( XR.ElementAt ( XL.Count ( ) - 1 ).X, 0 );
		Point p2 = new Point ( XR.ElementAt ( XL.Count ( ) - 1 ).X, 99 );
		Point p3 = new Point ( XL.ElementAt ( 0 ).X, 0 );
		Point p4 = new Point ( XL.ElementAt ( 0 ).X, 99 );
		Thread.Sleep ( delay );
		Dispatcher.Invoke ( new Action ( ( ) => {
			if (shortL != null) {
				canvas.Children.Remove ( shortL );
				lines.Remove ( shortL );
				canvas.Children.Remove ( l );
				lines.Remove ( l );
				canvas.Children.Remove ( l2);
				lines.Remove ( l2 );
				canvas.Children.Remove ( l3 );
				lines.Remove ( l3 );
			}

			shortL = getDrawLine ( p1, p2 );
			canvas.Children.Add ( shortL );
			lines.Add ( shortL );
			shortL.Stroke = Brushes.Black;
			shortL.StrokeThickness = 1;

			l = getDrawLine ( p3, p4 );
			canvas.Children.Add ( l );
			lines.Add ( l );
			l.Stroke = Brushes.Black;
			l.StrokeThickness = 1;

			l2 = getDrawLine ( p1, p3 );
			canvas.Children.Add ( l2 );
			lines.Add ( l2 );
			l2.Stroke = Brushes.Black;
			l2.StrokeThickness = 1;

			l3 = getDrawLine ( p2, p4 );
			canvas.Children.Add ( l3 );
			lines.Add ( l3 );
			l3.Stroke = Brushes.Black;
			l3.StrokeThickness = 1;

			l4 = getDrawLine ( new Point ( XL.ElementAt ( XL.Count ( ) - 1 ).X, 0 ), new Point ( XL.ElementAt ( XL.Count ( ) - 1 ).X, 99 ) );
			canvas.Children.Add ( l4 );
			lines.Add ( l4 );
			l4.Stroke = Brushes.DarkGoldenrod;
			l4.StrokeThickness = 1;
		} ) );

		LineWithPoints leftLWP= EffientClosestPair ( XL, YL );
		Dispatcher.Invoke ( new Action ( ( ) => {

			leftLWP.line = getDrawLine ( leftLWP.p1, leftLWP.p2 );
			if(!canvas.Children.Contains( leftLWP.line )) {
				canvas.Children.Add ( leftLWP.line );
				leftLWP.line.Stroke = Brushes.Green;
				lines.Add ( leftLWP.line );
			}

		} ) );
		Thread.Sleep ( delay);
		LineWithPoints rightLWP = EffientClosestPair ( XR, YR );
		Dispatcher.Invoke ( new Action ( ( ) => {

			rightLWP.line = getDrawLine ( rightLWP.p1, rightLWP.p2 );
			if (!canvas.Children.Contains (rightLWP.line )) {
				rightLWP.line.Stroke = Brushes.Green;
				canvas.Children.Add ( rightLWP.line );
				lines.Add ( rightLWP.line );

			}
		} ) );
		Thread.Sleep ( delay );
		LineWithPoints sigmaWidth = distance ( leftLWP.p1, leftLWP.p2 ) <= distance ( rightLWP.p1, rightLWP.p2 ) ? leftLWP : rightLWP;
		List<Point> Y = new List<Point> ( );
		foreach(Point p in PY) {
			if(Math.Abs( p.X - XL.ElementAt ( XL.Count ( ) - 1 ).X ) <= distance(sigmaWidth.p1,sigmaWidth.p2)) {
				Y.Add ( p );
			}
		}
		LineWithPoints centerLWP= getDByCom7 (Y);
		Dispatcher.Invoke ( new Action ( ( ) => {

			centerLWP.line = getDrawLine ( leftLWP.p1, leftLWP.p2 );

			centerLWP. line.Stroke = Brushes.Green;
			canvas.Children.Add ( centerLWP.line );
			lines.Add ( centerLWP.line );


		} ) );

		ret = distance ( sigmaWidth.p1, sigmaWidth.p2 ) <= distance ( centerLWP.p1, centerLWP.p2 ) ? sigmaWidth : centerLWP;
		Thread.Sleep ( delay );
		Dispatcher.Invoke ( new Action ( ( ) => {
			ret.line.Stroke = Brushes.Blue;
		} ) );
		Thread.Sleep ( delay );
		Dispatcher.Invoke ( new Action ( ( ) => {

			canvas.Children.Remove ( leftLWP.line );
			lines.Remove ( leftLWP.line );

			canvas.Children.Remove ( rightLWP.line );
			lines.Remove ( rightLWP.line );

			canvas.Children.Remove ( centerLWP.line );
			lines.Remove ( centerLWP.line );

			canvas.Children.Remove ( shortL );
			lines.Remove ( shortL );
			canvas.Children.Remove ( l );
			lines.Remove ( l );
			canvas.Children.Remove ( l2 );
			lines.Remove ( l2 );
			canvas.Children.Remove ( l3 );
			lines.Remove ( l3 );
		} ) );


		return ret;
	}
	private LineWithPoints getDByCom7 ( List<Point> Y) {
		LineWithPoints ret = new LineWithPoints ( );

		for (int i=0; i<Y.Count(); i++) {
			for(int j = i + 1; j < Y.Count ( ) && j < i + 8; j++) {
				if ((ret.p1.X ==0 &&ret.p1.Y==0&& ret.p2.X == 0 && ret.p2.Y == 0) || distance ( Y.ElementAt ( i ), Y.ElementAt ( j ) ) < distance ( ret.p1, ret.p2 )) {
					ret.p1 = Y.ElementAt ( i );
					ret.p2 = Y.ElementAt ( j );
				}
			}
		}
		return ret ;
	}
	private void start_Click ( object sender, RoutedEventArgs e ) {

		if (start.Content.ToString() == "停止演示") {
			start.Content = "开始演示";
			if(t!=null)
				t.Abort ( );
		} else {
			start.Content = "停止演示";
			switch (SelectALG.SelectedIndex) {
			case 0:
				BFALG ( );
				break;
			case 1:
				DivideSolution ( );
				break;
			}
		}


	}
}
public class LineWithPoints {
	public Point p1;
	public Point p2;
	public Line line;
}
}
